package day6;
import java.util.Arrays;
public class MergeSortMain {
    static  int[] assist; //辅助数组
    public static void main(String[] args) {
//        int[] a={80,4,50,7,11,3,6,2};
        int[] a={7,6,5};
//        int[] a={7,6};
        assist=new int[a.length];
        sort(a);
        System.out.println(Arrays.toString(a));
    }
    public  static  void sort(int[] a){
        int low=0,hight=a.length-1;
        sort(a,low,hight);
    }
    public  static  void sort(int[] a,int low,int hight){
        if(low>=hight)
            return;
        int mid;
        //对lo到hi之间的数据进行分为两个组
        mid=(low+hight)/2; //{80,4,50,7,11,3,6,2}; mid=7/2=3
        //对前半组数据进行排序
        sort(a,low,mid); //{80,4,50,7}
        //对后半组数据进行排序
        sort(a,mid+1,hight);//{11,3,6,2}
        //再把前后半组的两个组中的数据进行归并
        merge(a,low,mid,hight);
    }
    public  static  void merge(int[] a,int low,int mid,int hight){
        //定义三个指针，即数组下标
        int i=low;//记录辅助数组的下标，初始为low，即前半组的第一个数组元素的下标
        int p1=low;//记录待归并数组的下标，初始为low，即前半组的第一个数组元素的下标
        int p2=mid+1;//记录待归并数组的下标，初始为mid+1，即后半组的第一个数组元素的下标
        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        while (p1<=mid && p2<=hight){
            if(a[p1]<a[p2]){
                assist[i]=a[p1]; i++; p1++;
            }
            else {
                assist[i]=a[p2]; i++; p2++;
            }
        }
        //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1<=mid){
            assist[i]=a[p1];i++;p1++;
        }
        //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2<=hight){
            assist[i]=a[p2];i++; p2++;
        }
        //把辅助数组中的元素拷贝到原数组中
        for(int k=low;k<=hight;k++){
            a[k]=assist[k];
        }
    }
}
